package huaweiod.first;

import java.util.Arrays;

/**
 * 华为OD机试真题 Java 实现【租车骑绿岛】【2022.11 Q4新题】
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2023-06-21
 */
public class A_2023_02_CarRentalRideGreenIsland {

    /**
     * 最少需要多少辆单车（双人车）
     *
     * @param weights 每个人的重量
     * @param maxW    单车最大承重
     * @return
     */
    public static int minBicycle(int[] weights, int maxW) {
        if (weights == null || weights.length == 0) {
            return 0;
        }
        // 体重排序
        Arrays.sort(weights);
        int res = 0;
        int left = 0;
        int right = weights.length - 1;
        int sumW = weights[left] + weights[right];
        while (left < right) {
            if (sumW <= maxW) {
                res++;
                sumW = weights[++left] + weights[--right];
            } else {
                res++;
                sumW = weights[left] + weights[--right];
            }
        }
        if (left == right) {
            res++;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] weights = {3, 2, 2, 1};
        System.out.println(minBicycle(weights, 3));
    }
}
